1. Field of the Invention
The present invention relates to a method and apparatus for routing packets in an ad-hoc network, and more particularly to a position-based routing method and apparatus.
2. Description of the Related Art
In an ad-hoc network, there are two types of representative routing schemes, a reactive scheme and a proactive scheme. The reactive scheme is an on-demand scheme that sets up a route from a source node to a destination node whenever necessary. The proactive scheme is a table-driven scheme that sets up a route through the use of a routing table. Upon such a route setup, there may be a contradiction relationship (trade-off) in terms of time, resources, accuracy, etc, between the nodes.
Generally, a position-based routing scheme and a topology-based routing scheme include a combination of the reactive scheme and proactive scheme. Greedy Perimeter Stateless Routing (GPSR) is a representative position-based routing protocol. GPSR is composed of two forwarding modes: a greedy forwarding mode and a perimeter forwarding mode.
In the greedy forwarding mode, when a first node needs to transmit a packet to a destination, and one or more neighbor nodes are closer in distance to the destination node than to the first node, the first node transmits the packet to a neighbor node closest to the destination node among the neighbor nodes. In the perimeter forwarding mode, when a first node needs to transmit a packet to a destination node, and no neighbor node is closer to the destination node than to the first node, the first node transmits the packet to every neighbor node in sequence.
In GPSR, each node has a Global Positioning System (GPS), and stores the addresses and location information of neighbor nodes. For this reason, a route can be pruned through the use of a two-dimensional subgraph (i.e. a planar subgraph). The GPSR has been designed to transmit a packet in the greedy forwarding scheme, and to transmit a packet in the perimeter forwarding scheme when the greedy forwarding scheme cannot be applied.
Therefore, each node stores a neighbor node table, and periodically updates the neighbor node table. The neighbor nodes refers to nodes located within a one-hop transmission range with respect to a reference node. The neighbor node table includes information on neighbor nodes, and specifically, the neighbor node table contains information on neighbor nodes determined as nodes currently linked with the reference node, and information on neighbor nodes determined as nodes which are currently unlinked with the reference node, but have been linked with the reference node in the past. Whether a reference node is linked with a neighbor node is determined based on whether the reference node receives a beacon frame from the corresponding neighbor node within a predetermined time period. A beacon frame is periodically broadcast by each node, and includes location information of each node. When no beacon frame is received from a node included in a neighbor node table during the predetermined time period, information on the corresponding node is deleted from the neighbor node table. The predetermined time period may be greater than the broadcasting period of the beacon frame.
In the following description, a general procedure of transmitting a packet in the GPSR will be explained with reference to FIG. 1. FIG. 1 shows an ad-hoc network, which includes node i, node j, node k, node l, node m, node n, node o, and node D. In the ad-hoc network of FIG. 1, it is assumed that the neighbor nodes of node i are node j and node k, and node i has received a packet whose destination node is node D.
If it is determined that a link from node i to node j is in a normal state, node i routes the packet to node j, and then the packet is transferred from node j to node D, as a route shown as a dotted line in FIG. 1. In contrast, if it is determined that a link from node i to node j is not in a normal state, node i routes the packet to node k. Thus, the packet is transferred to node D via node k, node l, node m, node n, and node o, a route shown as a solid line in FIG. 1. That is, the transmission mode shifts to the perimeter forwarding mode.
Although a link between nodes is in a normal state, beacon frames broadcast from each node may collide with each other. The transmission success rate of a beacon frame is approximately 19.7% (1 beacon period, 5 nodes, 1-hop). The transmission success rate of a beacon frame has a tendency to decrease as the number of nodes increases. Nevertheless, when a predetermined number of beacon frames are lost, the forwarding mode may be immediately changed from the greedy forwarding mode to the perimeter forwarding mode, which may cause a mistake of setting up a route which detours around a short route. In the worst case, the packet does not arrive at the destination node.
Also, in the ad-hoc network, link breakage phenomena may be temporarily caused by obstacles, mobility, collision of beacon frames, noise, etc., and may be recovered to a normal state within a short time period. Nevertheless, the conventional GPSR is designed without taking into consideration when a temporary breakage of a link occurs, a route detouring around an actually existing link may be set up, so that network performance degradation, such as an increase in throughput and delay, may occur.